package com.wj.tree;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author wen.jie
 * @date 2021/8/24 15:31
 */
public class MinPriorityQueue<T extends Comparable<T>> implements Iterable<T>{
    //存储堆中的元素
    private T[] items;
    //记录堆中元素的个数
    private int N;


    public MinPriorityQueue(int capacity) {
        this.items = (T[]) new Comparable[capacity+1];
        this.N=0;
    }

    //获取队列中元素的个数
    public int size() {
        return N;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return N==0;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j])<0;
    }

    //交换堆中i索引和j索引处的值
    private void exch(int i, int j) {
        T tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }

    //往堆中插入一个元素
    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    //删除堆中最小的元素,并返回这个最小元素
    public T delMin() {
        T min = items[1];
        exch(1,N);
        N--;
        sink(1);
        return min;
    }

    private void swim(int k) {
        while (k > 1 && !less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && !less(j, j+1)) j++;
            if (less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    public Iterator<T> iterator() {
        return new HeapIterator();
    }

    private class HeapIterator implements Iterator<T> {
        private MinPriorityQueue<T> copy;
        public HeapIterator() {
            copy = new MinPriorityQueue<T>(size());
            for (int i = 1; i <= N; i++)
                copy.insert(items[i]);
        }

        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }
    }
}

